#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
#define endl "\n";

struct DSU{
    vector<int>f,s,siz;

    DSU(){}
    DSU(int n){
        init(n);
    }

    void init(int n){
        f.resize(n);
        s.resize(n);
        iota(f.begin(),f.end(),0);
        iota(s.begin(),s.end(),0);
        siz.assign(n,1);
    }

    int find(int x){
        while(x!=f[x]){
            x=f[x]=f[f[x]];
        }
        return x;
    }

    int find1(int x){
        while(x!=s[x]){
            x=s[x]=s[s[x]];
        }
        return x;
    }

    bool same(int x,int y){
        return find(x) == find(y);
    }

    bool merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return false;
        }
        if(x<y){
            swap(x,y);
        }
        siz[x]+=siz[y];
        f[y]=x;
        s[x]=y;
        return true;
    }

    int size(int x){
        return siz[find(x)];
    }
};


// 1 2 4 5 6 

// 1 2 3 5 4 6 7 9 8 10

void solve(){
    int n;
    cin>>n;
    DSU dsu(n+5);
    vector<int>vis(n+1,0);
    vector<int>l(n+5,0);
    vector<int>r(n+5,0);
    vector<int>num(n+1,0);
    vector<int>pos(n+1,0);
    
    for(int i=1;i<=n;i++){
        cin>>num[i];
        if(num[i]==1){
            r[0]=i;
        }
        if(num[i]==n){
            l[n+1]=i;
        }
        
        pos[num[i]]=i;
        if(vis[num[i]-1]){
            dsu.merge(num[i],num[i]-1);
            vis[num[i]]=1;
            r[num[i]-1]=i;
        }
        vis[num[i]]=1;
    }
    vector<int>vis1(n+1,0);
    for(int i=n;i>=1;i--){
        if(num[i]<n&&vis1[num[i]+1]){
            l[num[i]+1]=i;
        }
        vis1[num[i]]=1;
    }
    r[n]=n+1;
    // for(int i=1;i<=n;i++){
    //     cout<<l[i]<<" \n"[i==n];
    // }
    // for(int i=1;i<=n;i++){
    //     cout<<r[i]<<" \n"[i==n];
    // }
    // for(int i=1;i<=n;i++){
    //     cout<<cnt1[i]<<" \n"[i==n];
    // }
    // for(int i=1;i<=n;i++){
    //     cout<<cnt2[i]<<" \n"[i==n];
    // }
    for(int i=1;i<=n;i++){
        vis1[i]=0;
    }
    int ans=1e9;
    int temp1=0,temp2=n+1;
    int cnt1=0,cnt2=0;
    int num1=0,num2=n+1;
    for(int i=1;i<=n;i++){
        int fa=dsu.find(num[i]);
        int son=dsu.find1(num[i]);
        int cnt=0;
        if(vis1[fa]){
            continue;
        }
        while(r[num1]!=0&&r[num1]<pos[son]&&num1<son&&temp1<i){
            cnt1++;
            temp1=r[num1];
            num1++;
        }
        while(l[num2]>pos[fa]&&num2>fa&&temp2>pos[fa]){
            cnt2++;
            temp2=l[num2];
            num2--;
        }
        while(cnt2>0&&temp2<=pos[fa]){
            cnt2--;
            temp2=r[num2];
            num2++;
        }
        // cout<<cnt1<<" "<<cnt2<<endl;
        // cout<<son<<" "<<fa<<endl;
        vis1[fa]=1;
        if(cnt1!=son-1){
            cnt++;
        }
        if(cnt2!=n-fa){
            cnt++;
        }
        cnt+=son-1+n-fa-cnt1-cnt2;
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}